///**
// *
// */
//package leetCode;
//
//import java.util.ArrayList;
//import java.util.LinkedList;
//import java.util.Queue;
//
///**
// * @author zhong
// *
// */
//public class ShortestBridge {
//	int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
//
//	public int shortestBridge(int[][] A) {
//		ArrayList<ArrayList<int[]>> islands = find2Island(A);
//		ArrayList<int[]> smallIsland = islands.get(0).size() < islands.get(1).size() ? islands.get(0) : islands.get(1);
//		ArrayList<int[]> smallX = (new ArrayList<int[]>(smallIsland));
//		smallX.sort((a, b) -> (a[0] - b[0]));
//		ArrayList<int[]> smallY = (new ArrayList<int[]>(smallIsland));
//		smallY.sort((a, b) -> (a[1] - b[1]));
//
////		ArrayList<int[]> smallIsland
//	}
//
//	private ArrayList<ArrayList<int[]>> find2Island(int[][] a) {
//		ArrayList<ArrayList<int[]>> islands = new ArrayList<>(2);
//		int n = a.length;
//		boolean visited[][] = new boolean[n][n];
//		for (int i = 0; i < a.length; i++) {
//			for (int j = 0; j < a.length; j++) {
//				if (a[i][j] == 1 && !visited[i][j]) {
//					islands.add(BFS(a, new int[] { i, j }, visited));
//				}
//			}
//		}
//		return islands;
//	}
//
//	/**
//	 * BFS锟揭碉拷锟斤拷锟斤拷锟紹锟絤锟斤拷1
//	 *
//	 * @param a
//	 * @param curPos
//	 * @param visited
//	 * @return
//	 */
//	private ArrayList<int[]> BFS(int[][] a, int[] curPos, boolean[][] visited) {
//		ArrayList<int[]> res = new ArrayList<>();
//		Queue<int[]> queue = new LinkedList<>();
//		queue.add(curPos);
//		res.add(curPos);
//		while (!queue.isEmpty()) {
//			int[] pos = queue.poll();
//			for (int[] dir : dirs) {
//				int[] newPos = { pos[0] + dir[0], pos[1] + dir[1] };
//				if (inBound(newPos, a.length)) {
//					if (a[newPos[0]][newPos[1]] == 1 && !visited[newPos[0]][newPos[1]]) {
//						visited[newPos[0]][newPos[1]] = true;
//						queue.add(newPos);
//						res.add(newPos);
//					}
//				}
//			}
//		}
//		return res;
//	}
//
//	private boolean inBound(int[] newPos, int length) {
//		return newPos[0] < length && newPos[0] >= 0 && newPos[1] < length && newPos[1] >= 0;
//	}
//
//	/**
//	 * @param args
//	 */
//	public static void main(String[] args) {
//		// TODO Auto-generated method stub
//
//	}
//
//}
